import java.util.Arrays;

public class Demo1 {


    public static void main(String[] args) {
        int[][] mat = {{1,2,3},{4,5,6},{7,8,9}};
        int[][] dp = matrixBlockSum(mat,2);

    }


    public int[] missingTwo(int[] nums) {
        int tmp = 0;
        for(int x:nums)
            tmp^=x;
        for(int i=1;i<=nums.length+2;i++){
            tmp^=i;
        }

        int def = 0;
        while (true){
            if (((tmp>>def)&1)==1)break;
            else def++;
        }

        int[] ret = new int[2];
        for(int x:nums){
            if (((x>>def)&1)==1){
                ret[1]^=x;
            }else {
                ret[0]^=x;
            }
        }
        for(int i=1;i<=nums.length+2;i++){
            if (((i>>def)&1)==1){
                ret[1]^=i;
            }else {
                ret[0]^=i;
            }
        }

        return ret;




    }












    public int singleNumber(int[] nums) {
        int ret = 0;
        for(int i = 0;i<32;i++){
            int sum = 0;
            for(int x:nums){
                if (((x>>i)&1) == 1){
                    sum++;
                }
            }
            sum%=3;
            if (sum==1){
                ret |= 1<<i;
            }
        }
        return ret;



    }

    public int getSum(int a, int b) {

        while (b != 0){
            int x = a^b;
            int carry = (a&b)<<1;
            a = x;
            b = carry;
        }
        return a;

    }

    public int missingNumber(int[] nums) {
        int a = 0;
        for(int i=0;i<nums.length;i++){
            a^=nums[i];
        }
        for(int i=0;i<=nums.length;i++){
            a^=i;
        }
        return a;
    }

    public boolean isUnique(String astr) {
        if (astr.length()>26){
            return false;
        }
        int a = 0;
        char[] tmp = astr.toCharArray();
        for(int i=0;i<astr.length();i++){
            int x = tmp[i]-'a';
            if (((a>>x)&1) == 0){
                a|=1<<x;
            }else {
                return false;
            }

        }
        return true;

    }

    public static int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;

        //前缀和数组
        int[][] dp = new int[m+1][n+1];
        for (int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                dp[i+1][j+1] = dp[i][j+1] + dp[i+1][j] - dp[i][j] + mat[i][j];
            }
        }

        //计算answer数组
        int[][] answer = new int[m][n];
        for(int i = 0;i<m;i++){
            for(int j = 0;j<n;j++){
                //范围边界
                int mMin = Math.max(0,i-k)+1;
                int nMin = Math.max(0,j-k)+1;

                int mMax = Math.min(m-1,i+k)+1;
                int nMax = Math.min(n-1,j+k)+1;
                answer[i][j] = dp[mMax][nMax]
                        - dp[mMax][nMin-1]
                        - dp[mMin-1][nMax]
                        + dp[mMin-1][nMin-1];

            }
        }



        return answer;


    }



}
